package com.cdy.demo.algorithm;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

public class TraversalTree {


    public List<Integer> preTraversal(TreeNode node) {
        List<Integer> res = new ArrayList<>();
        Deque<TreeNode> deque = new ArrayDeque<>();
        TreeNode p = node;

        while (!deque.isEmpty() || p != null) {
            if (p != null) {
                res.add(p.val);
                deque.push(p);
                p = p.left;
            } else {
                p = deque.peek();
                deque.pop();
                p = p.right;
            }
        }
        return res;
    }

    public List<Integer> inTraversal(TreeNode node) {
        List<Integer> res = new ArrayList<>();
        Deque<TreeNode> deque = new ArrayDeque<>();
        TreeNode p = node;

        while (!deque.isEmpty() || p != null) {
            if (p != null) {
                deque.push(p);
                p = p.left;
            } else {
                p = deque.peek();
                deque.pop();
                res.add(p.val);
                p = p.right;
            }
        }
        return res;
    }


    public List<Integer> postTraversal(TreeNode node) {
        List<Integer> res = new ArrayList<>();
        Deque<TreeNode> deque = new ArrayDeque<>();
        TreeNode p = node;
        TreeNode l = null;
        while (!deque.isEmpty() || p != null) {
            if (p != null) {
                deque.push(p);
                p = p.left;
            } else {
                p = deque.peek();
                if (p.right == null || p.right==l) {
                    deque.pop();
                    res.add(p.val);
                    l = p;
                    p = null;
                } else {
                    p = p.right;
                }


            }
        }
        return res;
    }
}
